package com.leetcode.hashtable;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author: ZhouBert
 * @date: 2019/9/29
 * @description: 187. 重复的DNA序列
 * B
 * <p>
 * 所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
 * 编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。
 * <p>
 * 示例：
 * 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 * 输出：["AAAAACCCCC", "CCCCCAAAAA"]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/repeated-dna-sequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindRepeatedDnaSequences187 {

	/**
	 * 我的理解是字符串中所有的组合都是 A，C，G 和 T
	 * Time Limit Exceeded...
	 * todo: 在检索上，HashSet-O(1) 要远远快于 List (O(n))
	 *
	 * @param s
	 * @return
	 */
	public static List<String> findRepeatedDnaSequencesByList(String s) {
		List<String> result = new ArrayList<>();
		///超过一次，至少是11 (AAAAAAAAAA_A)
		if (s == null || s.length() < 11) {
			return result;
		}

		///char[] chars = s.toCharArray();
		///暂时存储 str 集合
		List<String> temp = new ArrayList<>();
		///双指针
		for (int i = 0, j = 10; j <= s.length(); i++, j++) {
			String tempStr = s.substring(i, j);
			if (temp.contains(tempStr)) {
				if (!result.contains(tempStr)) {
					result.add(tempStr);
				}
			} else {
				temp.add(tempStr);
			}
		}
		return result;
	}

	/**
	 * todo:34 ms	84.99%	47.6 MB
	 *
	 * @param s
	 * @return
	 */
	public static List<String> findRepeatedDnaSequencesByHashSet(String s) {
		List<String> result = new ArrayList<>();
		///超过一次，至少是11 (AAAAAAAAAA_A)
		if (s == null || s.length() < 11) {
			return result;
		}

		///暂时存储 str 集合
		HashSet<String> temp = new HashSet<>();
		HashSet<String> tempAns = new HashSet<>();
		///双指针
		for (int i = 0, j = 10; j <= s.length(); i++, j++) {
			String tempStr = s.substring(i, j);
			if (temp.contains(tempStr)) {
				if (!tempAns.contains(tempStr)) {
					tempAns.add(tempStr);
				}
			} else {
				temp.add(tempStr);
			}
		}
		return new ArrayList<>(tempAns);
	}

	/**
	 * TODO:通过位运算	http://www.debug8.com/java/t_2658.html
	 * todo:恩 好难啊！
	 * ？？？？
	 * @param s
	 * @return
	 */
	public static List<String> findRepeatedDnaSequencesByBitOperation(String s) {
		List<String> result = new ArrayList<String>();
		Set<Integer> firstTime = new HashSet<Integer>();
		Set<Integer> secondTime = new HashSet<Integer>();

		//也可以使用hashmap，但是用数组的话可以很好的提升性能
		char[] map = new char[26];
		map['A' - 'A'] = 0;//00
		map['C' - 'A'] = 1;//01
		map['G' - 'A'] = 2;//10
		map['T' - 'A'] = 3;//11

		char[] sArray = s.toCharArray();
		for (int i = 0; i < sArray.length - 9; i++) {
			int v = 0;
			for (int j = i; j < i + 10; j++) {
				v <<= 2;
				v |= map[sArray[j] - 'A'];
			}

			//这里使用了短路原理。也就是在字符串被第一次添加到firstTime的时候，将不会触发secondTime的添加
			//而第二次遍历时，会触发secondTime的添加行为并将子字符串添加到结果集中
			//超过第二次遍历以为这secondTime的添加会返回false，说明已经添加过，从而避免了重复添加至结果集
			if (!firstTime.add(v) && secondTime.add(v)) {
				result.add(s.substring(i, i + 10));
			}
		}
		return result;

	}

	public static void main(String[] args) {
		String s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
		///s = "AAAAAAAAAAAA";
		List<String> list = findRepeatedDnaSequencesByList(s);
		List<String> list1 = findRepeatedDnaSequencesByHashSet(s);
		List<String> list2 = findRepeatedDnaSequencesByBitOperation(s);
		System.out.println(list);
		System.out.println(list1);
		System.out.println(list2);

	}
}
